package 最小编辑代价;

/**
 * Created by hest0 on 2017/4/18.
 */
public class Main1 {
    public static void main(String[] args) {

    }

    public class MinCost {
        public int findMinCost(String A, int n, String B, int m, int c0, int c1, int c2) {
            if (A == null || B == null) return 0;
            char[] a = A.toCharArray(), b = B.toCharArray();
            int ic = c0, dc = c1, rc = c2;
            int row = A.length() + 1, col = B.length() + 1;
            int[][] dp = new int[row][col];
            //列初始化
            for (int i = 1; i < row; i++) {
                dp[i][0] = i * dc;
            }
            //行初始化
            for (int j = 1; j < col; j++) {
                dp[0][j] = j * ic;
            }
            //迭代
            for (int i = 1; i < row; i++) {
                for (int j = 1; j < col; j++) {
                    dp[i][j] = (a[i - 1] == b[j - 1]) ? dp[i - 1][j - 1] : dp[i - 1][j - 1] + rc;
                    dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + ic);
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + dc);
                }
            }
            return dp[row - 1][col - 1];
        }
    }

}
